package 简单.搜索.深度优先搜索;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个二叉树，计算 整个树 的坡度 。
 * <p>
 * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。
 * 如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
 * <p>
 * 整个树 的坡度就是其所有节点的坡度之和。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-tilt
 */
public class 二叉树的坡度_563 {

    //全局变量统计每个节点的坡度之和
    private int ans = 0;

    public static void main(String[] args) {


    }

    /**
     * 深度优先搜索+
     * 递归实现
     * 找到为空的节点之后，一层一层往上走
     *
     * @param curNode
     * @return
     */
    public int dfsFindTilt(TreeNode curNode) {
        //定义终止条件
        if (curNode == null) {
            return 0;
        }
        //当前节点其右子节点的所有值之和
        int rightTotal = dfsFindTilt(curNode.right);
        //当前节点其左子节点的所有值之和
        int leftTotal = dfsFindTilt(curNode.left);
        ans += Math.abs(rightTotal - leftTotal);
        //规定了这个函数求的是当前节点及其下级节点的所有值
        return rightTotal + leftTotal + curNode.val;
    }

    /**
     * 广度优先搜索
     *
     * @param root
     * @return
     */
    public static int bfsFindTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int count = 0;
        //定义一个队列
        Deque<TreeNode> deque = new ArrayDeque<>();
        //将根节点放入队列
        deque.addLast(root);
        while (!deque.isEmpty()) {
            //上一层节点的个数
            int size = deque.size();
            //上一层节点出队列
            while (size-- > 0) {
                TreeNode curTreeNode = deque.pollFirst();
                //将当前节点的左右节点入队列尾部
                int rightVal = 0;
                int leftVal = 0;
                if (curTreeNode.left != null) {
                    deque.addLast(curTreeNode.left);
                    leftVal = findNodeAllVal(curTreeNode.left);
                }
                if (curTreeNode.right != null) {
                    deque.addLast(curTreeNode.right);
                    rightVal = findNodeAllVal(curTreeNode.right);
                }
                //计算当前节点的的左右节点，各自所有的节点值之和，相减得到坡度
                count += Math.abs(rightVal - leftVal);
            }
        }
        return count;
    }

    public static int findNodeAllVal(TreeNode treeNode) {
        int count = treeNode.val;
        Deque<TreeNode> deque = new ArrayDeque<>();
        //将根节点放入队列
        if (treeNode != null) {
            deque.addLast(treeNode);
        }
        while (!deque.isEmpty()) {
            //上一层节点的个数
            int size = deque.size();
            //上一层节点出队列
            while (size-- > 0) {
                TreeNode curTreeNode = deque.pollFirst();
                if (curTreeNode.right != null) {
                    count += curTreeNode.right.val;
                    deque.addLast(curTreeNode.right);
                }
                if (curTreeNode.left != null) {
                    count += curTreeNode.left.val;
                    deque.addLast(curTreeNode.left);
                }
            }
        }
        return count;
    }

}
